package leetcode.p279;

/**
 * @author: trtan
 * @date: 2021-06-11 12:41
 **/
public class PerfectSquares {
    public int numSquares(int n) {
        // dp[i]代表凑成i最少需要多少个平方数
        int[] dp = new int[n + 1];
        // 由于所有i都能由i个i组成，故初始值均为i
        for (int i = 0; i <= n; i++) {
            dp[i] = i;
        }
        // 从大往小枚举，先用大的平方数凑，可以使得使用数量最少，因为从小的开始一开始使用的就是最多的数量
        for (int i = (int) Math.sqrt(n); i >= 1; i--) {
            //那么使用平方数i*i去凑成所有比它大的数
            for (int j = i * i; j <= n; j++) {
                // 虽然使用前面的平方数不一定能凑成（j - i * i）这个值，不过dp[j-i*i]初始值一定是最坏的情况
                // 如果dp[j-i*i]之前更新过，那么就能使得dp[j]更新为更小的值
                int pre = dp[j - i * i];
                if(dp[j] > pre + 1) {
                    dp[j] = pre + 1;
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(new PerfectSquares().numSquares(12));
    }
}
